public class Solution486 {
    public boolean PredictTheWinner(int[] nums) {
        if (nums.length%2==0){
            return true;
        }
        return dp(0,0,nums.length-1,nums)>=0;
    }

    private int dp(int turn, int start, int end,int[] nums) {
        if (start==end){
            return turn==0?nums[start]:-nums[start];
        }
        if (turn==0){
            return Math.max(nums[start]+dp(1,start+1,end,nums),nums[end]+dp(1,start,end-1,nums));
        }else{
            return Math.min(-nums[start]+dp(0,start+1,end,nums),-nums[end]+dp(0,start,end-1,nums));
        }
    }

    public static void main(String[] args) {
        System.out.println(new Solution486().PredictTheWinner(new int[]{1,5,2}));
    }
}
